package com.oocl.Model;

import com.oocl.Bean.Customer;

public class LinkedList<T extends Comparable> {
	private Node<T> headNode;
	private Node<T> tailNode;
	private int length;
	
	public LinkedList(){
		headNode = new Node(null);
		tailNode = headNode;
		length = 0;
	}
	
	public LinkedList(T value){
		headNode = new Node(value);
		tailNode = headNode;
		length = 1;
	}
	
	/**
	 * Get the length of the linkedlist
	 * @return length
	 */
	public int getLength(){
		return length;
	}
	
	/**
	 * Insert node into the list on tail
	 * @param data
	 */
	public void insertNode(T data){
		if(length == 0){
			Node node = new Node(data);
			headNode = node;
			tailNode = headNode;
			length++;
		}else{
			Node newNode = new Node(data);
			newNode.setPreNode(tailNode);
			tailNode.setNextNode(newNode);
			tailNode = newNode;
			length++;
		}
	}
	
	/**
	 * Delete the node in list by index
	 * @param index
	 * @return ifSucceed
	 */
	public boolean delteNode(int index){
		Node node = headNode;
		for(int i=0; i!=index-1; i++){
			if(node!=null){
				node = node.getNextNode();
			}else {
				return false;
			}
			
		}
		node.getPreNode().setNextNode(node.getNextNode());
		length--;
		return true;
	}
	
	/**
	 * sort the list
	 */
	public void sort(){
		if(length > 1){
			
			Node<T> p = headNode;
			for(int i=0; i<length-1; i++){
				p=headNode;
				for(int j=0; j<length-1-i; j++){
					if(p.getValue().compareTo(p.getNextNode().getValue()) > 0){
						T temp = p.getValue();
						p.setValue((T) p.getNextNode().getValue());
						p.getNextNode().setValue((T)temp);
					}
					p=p.getNextNode();
				}
			}
		}
	}
	
	/**
	 * search the customer
	 * @param 
	 */
	public T search(T c){
		
		sort();
		
		int left = 0;
		int right = length - 1;
		int mid = 0;

		while (left <= right) {
			mid = (right + left) / 2;
			if(getNode(mid).getValue().compareTo(c)==0){
				return getNode(mid).getValue();
			}else if(getNode(mid).getValue().compareTo(c) >0){
				right = -- mid;
			}else{
				left = ++mid;
			}
		}
		return null;
	}
	
	/**
	 * Get the node on the list by index
	 * @param index
	 * @return node
	 */
	public Node<T> getNode(int index){
		Node node = headNode;
		for(int i=0; i!=index; i++){
			node = node.getNextNode();
		}
		return node;
	}
	
}
